/*
 * Copyright (C), 2015-2018
 * FileName: Solution3
 * Author:   zhao
 * Date:     2018/10/9 22:28
 * Description: 3. 无重复字符的最长子串
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.HashSet;

/**
 * 〈一句话功能简述〉<br>
 * 〈3. 无重复字符的最长子串〉
 *
 * @author zhao
 * @date 2018/10/9 22:28
 * @since 1.0.1
 */
public class Solution3 {
  /**************************************
   * 3. 无重复字符的最长子串
   * 题目
   给定一个字符串，找出不含有重复字符的最长子串的长度。

   示例 1:

   输入: "abcabcbb"
   输出: 3
   解释: 无重复字符的最长子串是 "abc"，其长度为 3。
   示例 2:

   输入: "bbbbb"
   输出: 1
   解释: 无重复字符的最长子串是 "b"，其长度为 1。
   示例 3:

   输入: "pwwkew"
   输出: 3
   解释: 无重复字符的最长子串是 "wke"，其长度为 3。
   请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
   **************************************/

  /**************************************
   *
   * 想法：
   *    1. 暴力破解：锁定位置i、j，判断i和j之间是否有重复串，时间复杂度n3
   *    2. 滑动列表：还是锁定i、j,不过在遍历的同时，
   *          如果未发现重复字符串，将j往后移，
   *          如果发现重复字符串，将i往后移
   *          判断重复使用的是HashSet
   *
   * 我的做法
   *      超过41%的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *    NOT_ANSWER
   *    自己想出来的方法就是暴力破解，
   *    有想到加载过的字符不用重复，但是没有书写代码的思路
   *
   *    小批量字符可以使用数组代替hashSet
   *
   * ***********************************/
  public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    HashSet<Character> characters = new HashSet<>();
    int result = 0;
    int i = 0;
    int j = 0;

    while (i < n && j < n) {
      if (!characters.contains(s.charAt(j))) {
        characters.add(s.charAt(j));
        j++;
        result = Math.max(result, j - i);
      } else {
        characters.remove(s.charAt(i));
        i++;
      }
    }

    return result;
  }

  /**************************************
   * 比我好的答案 better
   * 这里使用了int[]代替了HashSet
   * ***********************************/
  public int better(String s) {
    int n = s.length(), ans = 0;
    int[] index = new int[128]; // current index of character
    // try to extend the range [i, j]
    for (int j = 0, i = 0; j < n; j++) {
      i = Math.max(index[s.charAt(j)], i);
      ans = Math.max(ans, j - i + 1);
      index[s.charAt(j)] = j + 1;
    }
    return ans;

  }

}
